package com.gxc.array;

import java.util.Arrays;

/**
 * LCP 40. 心算挑战
 * 「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，
 * 若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。
 * 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。
 * 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。
 */
public class MaxmiumScore {

    public static void main(String[] args) {
        //System.out.println(handle(new int[]{1,2,8,9}, 3));
        //System.out.println(handle(new int[]{3,3,1}, 3));

        //System.out.println(handle(new int[]{1,10,5,2,9}, 4));
        //System.out.println(handle(new int[]{1,3,4,5}, 4));
        System.out.println(handle(new int[]{5,1,10,6,2,5,4,5,7}, 7));
    }

    /**
     * 贪心
     * @param cards
     * @param cnt
     * @return
     */
    public static int handle(int[] cards, int cnt) {
        int l = cards.length;
        int[] even = new int[l];
        int[] odd = new int[l];
        int evenNum = 0;
        int oddNum = 0;
        for (int i = 0; i < l; i++) {
            if (cards[i]%2 == 0) {
                even[i] = cards[i];
                evenNum++;
            } else {
                odd[i] = cards[i];
                oddNum++;
            }
        }
        Arrays.sort(even);
        Arrays.sort(odd);
        int evenR = l-1;
        int oddR = l-1;
        int res = 0;
        //cnt 变为偶数
        if (cnt%2 == 1) {
            if (evenNum==0) return 0;
            res = res + even[evenR];
            cnt--;
            evenR--;
            evenNum--;
        }

        while (cnt>0) {
            if (evenNum>1 && oddNum>1) {
                if (even[evenR] + even[evenR-1] > odd[oddR] + odd[oddR-1]) {
                    res = res + even[evenR] + even[evenR-1];
                    evenR = evenR-2;
                    evenNum = evenNum -2;
                } else {
                    res = res + odd[oddR] + odd[oddR-1];
                    oddR = oddR - 2;
                    oddNum = oddNum -2;
                }
                cnt=cnt-2;
            } else if (evenNum>1) {
                res = res + even[evenR] + even[evenR-1];
                evenR = evenR-2;
                evenNum = evenNum -2;
                cnt=cnt-2;
            } else if (oddNum>1) {
                res = res + odd[oddR] + odd[oddR-1];
                oddR = oddR - 2;
                oddNum = oddNum -2;
                cnt=cnt-2;
            } else {
                return 0;
            }
        }
        return res;
    }

    /**
     * 一次遍历
     * 思路
     *
     * 将 cards 从大到小排序后，先贪心的将后 cnt 个数字加起来，若此时 sum 为偶数，直接返回即可。
     *
     * 若此时答案为奇数，有两种方案:
     *
     * 在数组前面找到一个最大的奇数与后 cnt 个数中最小的偶数进行替换；
     * 在数组前面找到一个最大的偶数与后 cnt 个数中最小的奇数进行替换。
     *
     * 两种方案选最大值即可。
     *
     */
    class Solution {
        public int maxmiumScore(int[] cards, int cnt) {
            Arrays.sort(cards);

            int ans = 0;
            int tmp = 0;
            int odd = -1, even = -1;
            int end = cards.length - cnt;
            for (int i = cards.length - 1; i >= end; i--) {
                tmp += cards[i];
                if ((cards[i] & 1) != 0) {
                    odd = cards[i];
                } else {
                    even = cards[i];
                }
            }

            if ((tmp & 1) == 0) {
                return tmp;
            }

            for (int i = cards.length - cnt - 1; i >= 0; i--) {
                if ((cards[i] & 1) != 0) {
                    if (even != -1) {
                        ans = Math.max(ans, tmp - even + cards[i]);
                        break;
                    }
                }
            }

            for (int i = cards.length - cnt - 1; i >= 0; i--) {
                if ((cards[i] & 1) == 0) {
                    if (odd != -1) {
                        ans = Math.max(ans, tmp - odd + cards[i]);
                        break;
                    }
                }
            }

            return ans;
        }
    }

    /**
     * 哈希
     * 思路
     *
     * 和上种方法思路一致，但时间复杂度的开销主要在排序上还可以进一步优化。
     * 注意到 cards[i] 的取值范围为 [1,1000]，
     * 因此可以开辟一个 val 数组，val[k] 表示值为 k 的元素个数。
     * 将遍历 cards 改为遍历 val，处理思路与方案一一致不再赘述。
     *
     */
    class Solution2 {
        public int maxmiumScore(int[] cards, int cnt) {
            int[] val = new int[1001];
            for (int i = 0; i < cards.length; i++) {
                val[cards[i]]++;
            }

            int ans = 0;
            int tmp = 0;
            int ed = -1;
            int odd = -1, even = -1;
            for (int i = 1000; i >= 1; i--) {
                if (val[i] == 0) {
                    continue;
                }

                if (val[i] > cnt) {
                    tmp += cnt * i;
                    cnt = 0;
                } else {
                    tmp += val[i] * i;
                    cnt -= val[i];
                    val[i] = 0;
                }

                if ((i & 1) != 0) {
                    odd = i;
                } else {
                    even = i;
                }

                if (cnt == 0) {
                    if (val[i] > 0) {
                        ed = i;
                    } else {
                        ed = i - 1;
                    }
                    break;
                }
            }

            if ((tmp & 1) == 0) {
                return tmp;
            }

            for (int i = ed; i >= 1; i--) {
                if (val[i] == 0) {
                    continue;
                }

                if ((i & 1) != 0) {
                    if (even != -1) {
                        ans = Math.max(ans, tmp - even + i);
                    }
                } else {
                    if (odd != -1) {
                        ans = Math.max(ans, tmp - odd + i);
                    }
                }
            }

            return ans;
        }
    }


}
